package leetcode.f1t100;

/**
 * 给出字符串s1,s2,s3,返回s1和s2是否可以交织成s3
 * https://leetcode.com/problems/interleaving-string
 *
 * @author lichx
 * @createTime 2024/2/21 14:38
 */
public class Q97_InterleavingString {
    public static void main(String[] args) {
        Q97_InterleavingString bean = new Q97_InterleavingString();
        System.out.println(bean.isInterleave("aa","ab","abaa"));
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        char[] chars3 = s3.toCharArray();
        if(chars1.length + chars2.length != chars3.length) {
            return false;
        }
        if(chars1.length == 0){
            return s2.equals(s3);
        }
        if(chars2.length == 0){
            return s1.equals(s3);
        }
        return isInterleave(chars1, chars2, chars3, new boolean[chars1.length+1][chars2.length+1]);
    }
    private boolean isInterleave(char[] chars1, char[] chars2, char[] chars3, boolean[][] dp){
        dp[0][0] = true;
        dp[1][0] = chars1[0] == chars3[0];
        dp[0][1] = chars2[0] == chars3[0];
        for (int i = 2; i <=chars1.length; i++) {
            dp[i][0] = dp[i-1][0] && chars1[i-1] == chars3[i-1];
        }
        for (int j = 2; j <=chars2.length; j++) {
            dp[0][j] = dp[0][j-1] && chars2[j-1] == chars3[j-1];
        }

        for (int i = 1; i <=chars1.length ; i++) {
            for (int j = 1; j <=chars2.length ; j++) {
                dp[i][j] = dp[i-1][j] && chars1[i-1] == chars3[i+j-1] || dp[i][j-1] && chars2[j-1] == chars3[i+j-1];
            }
        }
        return dp[chars1.length][chars2.length];
    }
}
